#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        vector<int>sst(stones.size()+1);
        vector<vector<int>>dp(stones.size()+1,vector<int>(stones.size()+1));
        int n=stones.size();
        for(int i=1;i<=stones.size();i++)
        {
            sst[i]=sst[i-1]+stones[i-1];
        }
       for(int i=n;i>=1;i--)
       {
        for(int j=i+1;j<=n;j++)
        {
            dp[i][j]=1e8;
            for(int k=i;k<j;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sst[j]-sst[i-1]);
            }
        }
       }
        return dp[1][n];
    }
};